// 使用队列实现栈
// 实现方法push 先进后出
// 实现方法pop 先进后出
// 实现方法top 取栈顶元素
var myStack = function () {
    this.stack = [];
}

myStack.prototype.push = function (x) {
    this.stack[this.stack.length] = x;
    return this.stack.length;
}

myStack.prototype.pop = function () {
    if (this.empty()) {
        return undefined
    }
    let popEle = this.stack(this.stack.length - 1);
    this.stack.length = this.stack.length - 1;
    return popEle
}

myStack.prototype.top = function () {
    return this.stack[this.stack.length - 1]

}

myStack.prototype.empty = function () {
    if (this.stack.length === 0) {
        return true
    } else {
        return false
    }
}


// 使用栈实现队列
// 同样实现push （） 先进先出
// 同样实现pop （） 先进先出
// 实现peek ====
class myQueen {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }
    push(x) {
        this.stack1.push(x)
    }
    pop() {
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop())
        }
        const item = this.stack2.pop()
        if (this.stack2.length) {
            while (this.stack2.length) {
                this.stack1.push(this.stack2.pop())
            }
        }
        return item
    }
    peek() {
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop())
        }
        const item = this.stack2[this.stack2.length - 1]
        if (this.stack2.length) {
            while (this.stack2.length) {
                this.stack1.push(this.stack2.pop())
            }
        }
        return item
    }
    empty() {
        return this.stack1.length === 0
    }
}

// 包含min函数的栈
// 同样实现pop, push 可以使用栈实现
function minStack() {
    this.stack = [];
    this.min = []
}
minStack.prototype.push = function (x) {
    this.stack.push(x);
    this.min.push(Math.min(this.min[this.min.length - 1], x))
}
minStack.prototype.pop = function () {
    let item = this.stack.pop();
    this.min.pop()
    return item;
}
minStack.prototype.pop = function () {
    return this.stack[this.stack.length - 1]
}
minStack.prototype.getmin = function () {
    return this.min[this.min.length - 1];
}

// 数组中第k个最大的数
let findKthLargest = function (nums, k) {
    nums.sort((a, b) => b - a).slice(0, k);
    return nums[k - 1]
}

let quickSort = (arr) => {
    quick(arr, 0, arr.length - 1)
}
let quick = (arr, left, right) => {
    let index;
    if (left < right) {
        index = partition(arr, left, right);
        if (left < index - 1) {
            quick(arr, left, index - 1)
        }
        if (index < right) {
            quick(arr, index, right)
        }
    }
}
let partition = (arr, left, right) => {
    var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
        i = left;
    j = right;

    while (i <= j) {
        while (arr[i] < datum) {
            i++
        }
        while (arr[j] > datum) {
            j--
        }
        if (i <= j) {
            swap(arr, i, j)
            i += 1;
            j -= 1
        }
    }
    return i
}
let swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp
}

// 寻找中位数（hard） 放弃
// 实现简单的计算器 （hard放弃）